package the.offer.leetcode;

import the.offer.Util.ListNode;

class SolutionOfList {
    /**
     * 2. 两数相加
     * 给出两个 非空 的链表用来表示两个非负的整数。
     * 其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;
            cur.next = new ListNode(v1 + v2 + carry);
            cur = cur.next;
            carry = (v1 + v2 + carry) / 10;
        }
        return dummy.next;
    }

    /**
     * 将两个有序链表 L1、L2 合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = l1, q = l2, curr = dummy;
        while (p != null && q != null) {
            if (p.val <= q.val) {
                curr.next = p;
                p = p.next;
            } else {
                curr.next = q;
                q = q.next;
            }
            curr = curr.next;
        }
        curr.next = p == null ? p : q;
        return dummy.next;
    }

    /**
     * 反转一个单链表
     */
    public static ListNode reverseList(ListNode head) {

        if (head == null || head.next == null)
            return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    // 无dummyHead
    public static ListNode removeElements(ListNode head, int val) {
        // 删除List开始处 node.val == val 的节点
        while (head != null && head.val == val) {
            ListNode deleteNode = head;
            head = head.next;
            deleteNode.next = null;
        }

        if (head == null)
            return null;

        ListNode prev = head;
        while (prev.next != null) {
            if (prev.next.val == val) {
                ListNode deleteNode = prev.next;
                prev.next = deleteNode.next;
                deleteNode.next = null;
            } // 删除prev.next，则prev不动
            else {
                prev = prev.next;
            }
        }
        return head;
    }

    // 有dummyHead
    public static ListNode removeElement2(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == val)
                prev.next = prev.next.next;
            else
                prev = prev.next;
        }
        return dummyHead.next;
    }

    // 递归解法
    public static ListNode removeElement3(ListNode head, int val) {
        if (head == null)
            return null;
        head.next = removeElement3(head.next, val);
        if (head.val == val)
            return head.next;
        else
            return head;
    }


    /**
     * 链表排序
     */
    public static ListNode sortList(ListNode head) {
        return null;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 2, 3, 2, 1};
        ListNode list = new ListNode(arr);
        sortList(list);
        System.out.println(list.toString());

//        SolutionOfList.removeElement3(list, 2);
//        System.out.println(list.toString());

//        list = reverseList(list);
//        System.out.println(list.toString());
    }
}
